// 在一个 n * m 的二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。
// 请完成一个高效的函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。

// 示例:
// 现有矩阵 matrix 如下：

// [
//   [1,   4,  7, 11, 15],
//   [2,   5,  8, 12, 19],
//   [3,   6,  9, 16, 22],
//   [10, 13, 14, 17, 24],
//   [18, 21, 23, 26, 30]
// ]
// 给定 target = 5，返回 true。

// 给定 target = 20，返回 false。

// 来源：力扣（LeetCode）
// 链接：https://leetcode.cn/problems/er-wei-shu-zu-zhong-de-cha-zhao-lcof
// 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

/**
 * @param {number[][]} matrix
 * @param {number} target
 * @return {boolean}
 */

// 根据这个矩阵的纵向横向数字大小变化特征
// 从左下角开始判断,该位置数字大于目标时,向上移动一位
// 当位置数字小于目标时,向右移动一位
var findNumberIn2DArray = function (matrix, target) {
  if (!matrix.length) return false;
  let row = matrix.length - 1;
  let colume = 0;
  while (row >= 0 && colume < matrix[0].length) {
    if (matrix[row][colume] === target) {
      return true;
    } else if (matrix[row][colume] > target) {
      row--;
    } else {
      colume++;
    }
  }
  return false;
};

let test = [
  [1, 2, 3, 4, 5],
  [6, 7, 8, 9, 10],
  [11, 12, 13, 14, 15],
  [16, 17, 18, 19, 20],
  [21, 22, 23, 24, 25],
];
console.log(findNumberIn2DArray(test, 19));
